interface IObj {
  name: string;
  weight: number;
  value: number;
}
interface IRowItem {
  components: IObj[];
  total: number;
  tag?: string;
}

export const getBiggestValueInpcg =(capacity: number, objs: IObj[]) => {
  const objsLen = objs.length;
  const matrix: IRowItem[][] = [];

  for (let i = 0; i <= objsLen; i++) {
    matrix.push([]);
    const row: IRowItem[] = matrix[i];
    for (let j = 0; j <= capacity; j++) {
      if (j === 0 || i === 0) {
        row.push({
          components: [],
          total: 0,
          tag: 'no'
        });
      } else {
        const component = objs[i - 1];
        let currentV = matrix[i - 1][j];
        
        if (component.weight <= j) {
          const trace: IRowItem = (j - component.weight) >= 0 ? {
            components: matrix[i - 1][j - component.weight].components.concat([component]),
            total: matrix[i - 1][j - component.weight].total + component.value
          } : {
            components: [],
            total: 0
          };
          
          if (trace.total >= currentV.total) {
            currentV =  trace;
          }
        }

        row.push(currentV);
      }
    }
  }
  
  return matrix[objs.length - 1][capacity];
};

export const getBiggestValueInpcgFraction = (capacity: number, objs: IObj[]) => {
  const objsSort = objs.sort((a, b) => a.weight - b.weight);
  let value = 0;
  const result: {
    obj: IObj;
    number: number;
  }[] = [];
  let capacityCache = capacity;

  for (let i = 0; i < objsSort.length; i++) {
    capacityCache-=objsSort[i].weight;
    if (capacityCache >= 0) {
      result.push({
        obj: objsSort[i],
        number: 1
      });
      value+=objsSort[i].value;
    } else {
      capacityCache+=objsSort[i].weight;
      const percent = capacityCache / objsSort[i].weight;
      result.push({
        obj: objsSort[i],
        number: percent
      });
      value+=(percent * objsSort[i].value);
      break;
    }
  }

  return {
    components: result,
    value
  };
};
